from collections import deque
import copy

# ______________ Создаем польскую постфиксную нотацию по алгоритму Дейкстры (+ вспомогательные функции) ________________

def dijkstra_shunting_yard(vyr):  # через два листа
    priority = {"(": 0, ")": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    pol_not = list()  # сюда пишем польскую нотацию
    oper_stack = list()
    buff = turn_to_int(vyr)  # переводим числа в массиве из строк в int цифры
    # buff = turn_to_double(vyr)    #переводим числа в массиве из строк в double (хотя на самом деле float) цифры
    for elem in buff:
        if isinstance(elem, float) or isinstance(elem, int):
            pol_not.append(elem)
        elif elem == "+" or elem == "-" or elem == "*" or elem == "/":
            i = len(oper_stack) - 1
            while i >= 0 and oper_stack[i] != "(" and priority[oper_stack[i]] >= priority[elem]:
                pol_not.append(oper_stack.pop())
                i -= 1
            oper_stack.append(elem)
        elif elem == "(":
            oper_stack.append(elem)
        elif elem == ")":
            i = len(oper_stack) - 1
            while i > 0 and oper_stack[i] != "(":
                pol_not.append(oper_stack.pop())
                i -= 1
            if i == 0 and oper_stack[i] != "(":
                print("Ошибка в записи выражения! Скобки не совпадают.")
            if oper_stack[i] == "(":
                oper_stack.pop()
        else:
            print("Ошибка! недопустимая дичь.")
    while len(oper_stack) != 0:
        pol_not.append(oper_stack.pop())
    print("Польская нотация выражения (метод списков):", *pol_not)
    return pol_not


def dijkstra_shunting_yard_deque(vyr):  # с помощью дека
    priority = {"(": 0, ")": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    pol_not = deque()  # сюда пишем польскую нотацию
    buff = turn_to_int(vyr)  # переводим числа в массиве из строк в int цифры
    # buff = turn_to_double(vyr)    #переводим числа в массиве из строк в double (хотя на самом деле float) цифры
    for elem in buff:
        if isinstance(elem, float) or isinstance(elem, int):
            pol_not.append(elem)
        elif elem == "+" or elem == "-" or elem == "*" or elem == "/":
            i = 0
            while (not isinstance(pol_not[i], float)) and (not isinstance(pol_not[i], int)) and pol_not[i] != "(" and \
                    priority[pol_not[i]] >= priority[elem]:
                pol_not.append(pol_not.popleft())
            pol_not.appendleft(elem)
        elif elem == "(":
            pol_not.appendleft(elem)
        elif elem == ")":
            i = 0
            while (not isinstance(pol_not[i], float)) and (not isinstance(pol_not[i], int)) and pol_not[i] != "(":
                pol_not.append(pol_not.popleft())
            if isinstance(pol_not[i], float) or isinstance(pol_not[i], int):
                print("Ошибка в записи выражения! Скобки не совпадают.")
            if pol_not[i] == "(":
                pol_not.popleft()
        else:
            print("Ошибка! недопустимая дичь.")
    i = 0
    while (not isinstance(pol_not[i], float)) and (not isinstance(pol_not[i], int)):
        pol_not.append(pol_not.popleft())
    print("Польская нотация выражения (метод дека):", *pol_not)
    return pol_not


def turn_to_int(vyr):
    buff = vyr.split()
    for i in range(0, len(buff)):
        if buff[i].isdigit():
            buff[i] = int(buff[i])
    return buff


def turn_to_double(vyr):
    buff = vyr.split()
    for i in range(0, len(buff)):
        if buff[i].isdigit():
            buff[i] = float(buff[i])
    return buff


# ___________________________________ Обсчитываем польскую постфиксную нотацию _________________________________________

def pol_calc(pol_note):
    buff = deque()
    while len(pol_note) >= 3:
        i = len(pol_note) - 1
        while i >= 0:
            if pol_note[i] == '+' or pol_note[i] == '-' or pol_note[i] == '*' or pol_note[i] == '/':
                if (isinstance(pol_note[i - 1], float) or isinstance(pol_note[i - 1], int)) and (
                        isinstance(pol_note[i - 2], float) or isinstance(pol_note[i - 2], int)):
                    if pol_note[i] == '+':
                        buff.appendleft(pol_note[i - 2] + pol_note[i - 1])
                    elif pol_note[i] == '-':
                        buff.appendleft(pol_note[i - 2] - pol_note[i - 1])
                    elif pol_note[i] == '*':
                        buff.appendleft(pol_note[i - 2] * pol_note[i - 1])
                    elif pol_note[i] == '/':
                        buff.appendleft(pol_note[i - 2] / pol_note[i - 1])
                    i -= 2
                else:
                    buff.appendleft(pol_note[i])
            else:
                buff.appendleft(pol_note[i])
            i -= 1
        pol_note = copy.copy(buff)
        buff.clear()
    print("Выражение в польской нотации равно:", *pol_note)
    return pol_note


# ______________________________ MAIN _______________________________________

# stroka = "2 * 3 + ( 4 * ( 6 * 7 ) + 2 ) * 5"
stroka = "( 54 + 6 ) / 10 * 7 - ( 84 - 59 ) + ( 6 * 5 ) / 3"
# stroka = "( 8 * 8 - 24 ) / 10 + ( 32 / 4 * 5 ) - 2 * 7"

print("Значение выражения найденное с помощью eval:", eval(stroka))
print(" ")

pol = dijkstra_shunting_yard(stroka)
print(" ")

dijkstra_shunting_yard_deque(stroka)
print(" ")

a = pol_calc(pol)
